In this work, we try to understand the differences between exact and approximate inference algorithms in structured prediction. We compare the estimation and approximation error of both underestimate and overestimate models. The result shows that, from the perspective of learning errors, performances of approximate inference could be as good as exact inference. The error analyses also suggest a new margin for existing learning algorithms. Empirical evaluations on text classification, sequential labelling and dependency parsing witness the success of approximate inference and the benefit of the proposed margin.

This paper is on the important topic of learning with approximate inference. Previous work, e.g., Kulesza and Pereira (2007), has demonstrated the importance of matching parameter update rules and inference approximation methods. This paper presents a new update rule based on PAC Bayes bounds, which is fairly agnostic to the inference algorithm used -- it assumes a multiplicative error bound on model score and supports both over and under approximations. The example given in section 3.2 is a great illustration of how approximation error is more subtle than we might think it is. Sometimes an approximate predictor can fit the training data better because it represents a different family of functions!

In this work, we try to understand the differences between exact and approximate inference algorithms in structured prediction. We compare the estimation and approximation error of both underestimate and overestimate models. The result shows that, from the perspective of learning errors, performances of approximate inference could be as good as exact inference. The error analyses also suggest a new margin for existing learning algorithms. Empirical evaluations on text classification, sequential labelling and dependency parsing witness the success of approximate inference and the benefit of the proposed margin.